There are many contemporary encoding methods available for encoding data, and corresponding methods for decoding data. However, none of these known methods is optimally suited for all different types of images, video, audio, graphics, Unicode or binary data or data areas. Examples of known contemporary encoding methods are provided in Table 1.
TABLE 1Contemporary known encoding methodsMethodReferenceDiscrete cosineWikipedia, the free encyclopedia (accessed Apr. 26, 2013).transform (DCT)URL: http://en.wikipedia.org/wiki/Discrete_cosine_transformWavelet transformWikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Wavelet transformPalette (computing)Wikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Palette %28computing%29
Typical image and video encoding methods, for example as provided in Table 2, are reasonably effective for use in compressing natural image content, but less satisfactory for compressing other types of content, for example desktop images, animations, graphics or natural content that contains multiple different values but is still somehow structured.
TABLE 2Other known contemporary data encoding methodsMethodReferenceJPEGWikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/JPEGJPEG 2000Wikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/JPEG_2000WebPGoogle Developers (accessed Apr. 26, 2013).URL: https://developers.google.com/speed/webp/H.264/Wikipedia, the free encyclopedia (accessed Apr. 26, 2013).MPEG-4URL: http://en.wikipedia.org/wiki/H.264/MPEG-4_AVCAVCThe WebMWelcome to the WebM Project (accessed Apr. 26, 2013).ProjectURL: http://www.webmproject.org/VC-1Wikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/VC-1
Other encoding methods such as GIF and PNG, as provided in Table 3, are also able to handle certain specific types of encoding tasks effectively, but become less appropriate if data corresponding to a given image to be encoded includes many different types of content, or a considerable amount of mutually similar content, or contents which are potentially susceptible to cause errors during subsequent reconstruction during decoding of encoded data. For example, if the given image includes natural objects, namely objects with spatially detailed subtle information, GIF as an encoding method creates problematic artefacts and potentially large errors during encoding. Moreover, PNG as an encoding method employs a large quantity of bits of data for encoding “noise-like” features, thereby potentially resulting in poorer data compression performance. Furthermore, individual transform-based methods such as DCT and wavelet methods are not suitable for structured content in the given image, see Table 1.
TABLE 3Other known contemporary data coding methodsMethodReferenceGraphics InterchangeWikipedia, the free encyclopedia (accessed Apr. 26, 2013).Format (GIF)URL: http://en.wikipedia.org/wiki/Graphics_Interchange_FormatPortable NetworkWikipedia, the free encyclopedia (accessed Apr. 26, 2013).Graphics (PNG)URL: https://en.wikipedia.org/wiki/Portable Network Graphics
Known contemporary Run Length Encoding (RLE) is capable of efficiently encoding multiple similar data values that are adjacent; however, RLE otherwise exhibits some limitations and problems related to the method itself and its optimization, for example in respect of coping with periodic data values. Additionally, a delivery mechanism for information employed in RLE utilizes more values than is often desirable, in an event that horizontal lines are coded into 2D-blocks by RLE. Moreover, vertical or other line directions are even more difficult to encode using RLE-based methods.
Encoding data pursuant to a well known contemporary H.264 method employs intra-block prediction, wherein an extrapolation technique is utilized by using outside values of data blocks by delivering an associated selected prediction direction, although no other extrapolation-related value for a given block is delivered. As a consequence, the H.264 method cannot validate such selection by using a validation of one or more bits. Moreover, there is not provided a feature of delivering an additional extrapolation method related by value, for example by way of a delta value or gradient value, which can be used to improve extrapolation results. In the H.264 method, only prediction errors are supported, but are not related to extrapolation computations or their implementation.
It will be appreciated that aforementioned methods are not well adapted for all types of data block-based encoding tasks. None of the aforesaid known methods is optimally suited for all different types of images, video, audio, graphics, Unicode or binary data or data areas. For that reason, a new method is required to complement the selection of encoding methods so that all kinds of data can be compressed more efficiently.
In a published PCT patent application WO 2012100047 (“Methods and apparatus for geometric-based intra prediction”, Applicant—Thomson Licensing), there are described methods and apparatus for geometric-based intra prediction, which is expressed by an intra block coding scheme with geometric-based intra prediction to improve an intra prediction accuracy and an intra coding efficiency. A prediction direction is derived based upon a geometric structure of neighbouring surrounding pixels. The methods and apparatus are based upon surrounding pixels of a given block boundary which are used for identifying a local geometric pattern, and to derive an intra prediction mode for a current block. A similar operation is performed at a decoder to derive the prediction mode.
In another published US patent application US 20110293002 (“Methods and apparatus for transform selection in video encoding and decoding”, Applicant—Thomson Licensing, Inventor—Joel Sole) there are described methods and apparatus for transform selection in video coding, which is expressed by using a set of transforms, namely two or more transforms, to encode an image or video by choosing a best transform for each block. The set of transforms may be optimized or designed for a range of statistics or image/video patterns. The methods and apparatus also involve how to select a best transform and proper signaling of the selected transform, so that a video decoder can recover selected information efficiently.
Further, in a published US patent application US20070182728 (“Image display system, image display method, image display program, recording medium, data processing apparatus, and image display apparatus”, Inventor—Toshiki Fujimori) there is described an image display system which includes a data processing apparatus, an image display apparatus, and a communication unit for processing an image data. The data processing apparatus encodes different types of content data of the image data. Encoding of the content data is based upon the type of content data. Thereafter, the encoded content data is transmitted to the image display apparatus by the communication unit. The image display unit decodes the content data of the image data to display the image.
In a granted U.S. Pat. No. 8,149,910 (“Image encoding/image decoding method and image encoding/image decoding apparatus”, Inventor—Takeshi Chujoh, Akiyuki Tanizawa), there are described an image coding method and apparatus which operates by dividing an input picture into a plurality of pixel block signals and encoding them. Then, there is performed intra prediction for extrapolating or interpolating a prediction pixel using reference pixels changed in number according to a distance between the prediction pixel and a reference pixel in plural prediction modes, wherein each mode represents a corresponding prediction direction. Thereby, there is generating a predictive image signal by extrapolating or interpolating the prediction pixel and calculating a prediction error signal from the pixel block signal and the predictive image signal. Hence, there is selected one prediction mode of the plural prediction modes using the prediction error signal, and there is performed entropy-coding using the prediction error signal based on the selected prediction mode.
In a granted U.S. Pat. No. 6,317,515 (“Method and apparatus for encoding and decoding a data stream using inferential techniques”, Applicant—Avid Technology, Inc., Inventor—Jeffrey D. Kurtze, Joseph H. Rice, Robert Gonsalves, Chia-Sheng Chou), there is described an encoding/decoding method and apparatus which is exemplified by encoding an input data stream for compression purposes, and decoding the compressed data stream for use. The encoding process identifies trends in the data stream, and stores information about the trends in an encoded block. The decoder infers the type of the components associated with the encoded block according to an original order of components in the data stream, the order of the encoded block in the sequence of encoded blocks and a number of the corresponding components encoded by each of the preceding encoded blocks. Once the type of the component is determined, the decoder reconstructs the data stream by translating the encoded trend information into component values.
In the following description, acronyms and abbreviations will be employed as provided in Table 4.
TABLE 4Abbreviations and acronymsAbbrevi-ation oracronymDefinitionDCTDiscrete cosine transformDPCMDifferential pulse-code modulationWikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Differential pulse-codemodulationEMEntropy Modifier invented by Ossi Kalevo, patent pendingH.264H.264: this an advanced Video Coding (AVC) which is anindustry standard for video compressionJPEGJoint Photographic Experts Group's lossy compressionmethodJPEG2000Joint Photographic Experts Group's renewed compressionmethodOdeltaDelta coding method invented by Ossi Kalevo, patentpendingPCMPulse-code modulation:Wikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Pulse-code_modulationRDRate DistortionWikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Rate%E2%80%93distortionoptimizationRLERun-length encodingWikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Run-length_encodingSRLESplit run-length encoding invented by Tuomas Kärkkäinenand Ossi Kalevo, patent pendingVC-1An evolution of the conventional DCT-based video codecdesignVLCVariable-length code:Wikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Variable-length codeVQVector quantization:Wikipedia, the free encyclopedia (accessed Apr. 26, 2013).URL: http://en.wikipedia.org/wiki/Vector_quantizationWebMOpen video format for the webWebPAn image format that provides lossless and lossycompression for images on the web